home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 244_01 / one42.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-24  |  7.5 KB  |  272 lines
  1.  
  2. /* ONE42.C */
  3. /* program to analyze the de Bruijn diagram of a cellular */
  4. /* automaton and report all the periodic states. */
  5. /* version for totalistic (4,2), first generation */
  6. /* [Harold V. McIntosh, 4 May 1987] */
  7.  
  8. # include <stdio.h>
  9.  
  10. # define MC    11                /* maximum number of columns */
  11. # define NS     16                /* number of distinct sums */
  12. # define NW    24                /* pause after so many lines */
  13.  
  14. char arry[4][4][4][4][4];
  15. int  rule[NS] = 0,1,0,0,1,2,1,2,3,3,1,2,1,0,0,3;
  16. int  nc, nl;
  17.  
  18. main() {char c; int i;
  19.  
  20. printf("Rule number:\n\n");
  21. printf("0....1....2....3\n");
  22. for (i=0; i<NS; i++) rule[i]=getchar()-'0';
  23.  
  24. nc=0;
  25. nl=0;
  26.  
  27. do {
  28. printf("  a=still  b=slowglider  c=fastglider  0,1,2,3=constant  q=quit\015");
  29. c=kbdin();
  30. if (c=='q') break;
  31. switch (c) {
  32. case 'a':
  33. kwait(0); printf("Sequences satisfying the condition (1,0):"); kwait(0);
  34. pass1a(); pass2i(); pass2o(); pass4(); break;
  35. case 'b':
  36. kwait(0); printf("Sequences satisfying the condition (1,1):"); kwait(0);
  37. pass1b(); pass2i(); pass2o(); pass4(); break;
  38. case 'c':
  39. kwait(0); printf("Sequences satisfying the condition (1,2):"); kwait(0);
  40. pass1c(); pass2i(); pass2o(); pass4(); break;
  41. case '0':
  42. kwait(0); printf("Sequences mapping into a constant string of 0's:"); kwait(0);
  43. pass1x(0); pass2i(); pass2o(); pass4(); break;
  44. case '1':
  45. kwait(0); printf("Sequences mapping into a constant string of 1's:"); kwait(0);
  46. pass1x(1); pass2i(); pass2o(); pass4(); break;
  47. case '2':
  48. kwait(0); printf("Sequences mapping into a constant string of 2's:"); kwait(0);
  49. pass1x(2); pass2i(); pass2o(); pass4(); break;
  50. case '3':
  51. kwait(0); printf("Sequences mapping into a constant string of 3's:"); kwait(0);
  52. pass1x(3); pass2i(); pass2o(); pass4(); break;
  53. default: break; };
  54.  } while (i!='q');
  55.  
  56. } /* end main */
  57.  
  58. /* mark all links satisfying the criterion (1,0) */
  59. pass1a() {int i0,i1,i2,i3,i4
  60. printf(" pass1a\015");
  61. for (i0=0; i0<4; i0++) {
  62. for (i1=0; i1<4; i1++) {
  63. for (i2=0; i2<4; i2++) {
  64. for (i3=0; i3<4; i3++) {
  65. for (i4=0; i4<4; i4++) {
  66. arry[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4]==i2?'Y':'N';
  67. };};};};};
  68. }
  69.  
  70. /* mark all links satisfying the criterion (1,1) */
  71. pass1b() {int i0,i1,i2,i3,i4
  72. printf(" pass1b\015");
  73. for (i0=0; i0<4; i0++) {
  74. for (i1=0; i1<4; i1++) {
  75. for (i2=0; i2<4; i2++) {
  76. for (i3=0; i3<4; i3++) {
  77. for (i4=0; i4<4; i4++) {
  78. arry[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4]==i1?'Y':'N';
  79. };};};};};
  80. }
  81.  
  82. /* mark all links satisfying the criterion (1,2) */
  83. pass1c() {int i0,i1,i2,i3,i4
  84. printf(" pass1c\015");
  85. for (i0=0; i0<4; i0++) {
  86. for (i1=0; i1<4; i1++) {
  87. for (i2=0; i2<4; i2++) {
  88. for (i3=0; i3<4; i3++) {
  89. for (i4=0; i4<4; i4++) {
  90. arry[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4]==i0?'Y':'N';
  91. };};};};};
  92. }
  93.  
  94. /* Pass 1x marks all the configurations mapping into a constant */
  95. pass1x(c) int c; {int i0,i1,i2,i3,i4;
  96. printf(" Pass1x\015");
  97. for (i0=0; i0<4; i0++) {
  98. for (i1=0; i1<4; i1++) {
  99. for (i2=0; i2<4; i2++) {
  100. for (i3=0; i3<4; i3++) {
  101. for (i4=0; i4<4; i4++) {
  102. arry[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4]==c?'Y':'N';
  103.   };};};};}; }
  104.  
  105. /* flag links which have an incoming arrow */
  106. pass2i() {int i0, i1, i2, i3, i4, m;
  107. do {
  108. printf(" pass2i\015");
  109. for (i0=0; i0<4; i0++) {
  110. for (i1=0; i1<4; i1++) {
  111. for (i2=0; i2<4; i2++) {
  112. for (i3=0; i3<4; i3++) {
  113. for (i4=0; i4<4; i4++) {
  114. if ((arry[i0][i1][i2][i3][i4]&0x5F)=='Y')
  115.  {for (m=0; m<4; m++) arry[i1][i2][i3][i4][m]|=0x20;};
  116. };};};};};
  117. } while (pass3()!=0);
  118. }
  119.  
  120. /* flag links which have an outgoing arrow */
  121. pass2o() {int i0, i1, i2, i3, i4, m;
  122. do {
  123. printf(" pass2o\015");
  124. for (i0=0; i0<4; i0++) {
  125. for (i1=0; i1<4; i1++) {
  126. for (i2=0; i2<4; i2++) {
  127. for (i3=0; i3<4; i3++) {
  128. for (i4=0; i4<4; i4++) {
  129. if ((arry[i0][i1][i2][i3][i4]&0x5F)=='Y')
  130.  {for (m=0; m<4; m++) arry[m][i0][i1][i2][i3]|=0x20;};
  131. };};};};};
  132. } while(pass3()!=0);
  133. }
  134.  
  135. /* erase flags, mark survivors, count channges */
  136. pass3() {int i0, i1, i2, i3, i4, l;
  137. l=0;
  138. printf(" pass3 \015");
  139. for (i0=0; i0<4; i0++) {
  140. for (i1=0; i1<4; i1++) {
  141. for (i2=0; i2<4; i2++) {
  142. for (i3=0; i3<4; i3++) {
  143. for (i4=0; i4<4; i4++) {
  144. switch (arry[i0][i1][i2][i3][i4]) {
  145.     case 'y': arry[i0][i1][i2][i3][i4]='Y'; break;
  146.     case 'Y': arry[i0][i1][i2][i3][i4]='N'; l=1; break;
  147.     case 'n': case 'N': arry[i0][i1][i2][i3][i4]='N'; break;
  148.     default: break; };
  149. };};};};};
  150. return l;
  151. }
  152.  
  153. /* pass4 - print loops which remain */
  154. pass4() {
  155. int i0, i1, i2, i3, i4;
  156. int j0, j1, j2, j3, j4, k, l, m;
  157. printf(" pass4 \015");
  158. for (i0=0; i0<4; i0++) {
  159. for (i1=0; i1<4; i1++) {
  160. for (i2=0; i2<4; i2++) {
  161. for (i3=0; i3<4; i3++) {
  162. for (i4=0; i4<4; i4++) {
  163. j1=i1; j2=i2; j3=i3; j4=i4; l=0; m=0;
  164. do {
  165.         if (arry[0][j1][j2][j3][j4]=='Y')
  166.     {arry[0][j1][j2][j3][j4]='y';
  167.     k=j4; j4=j3; j3=j2; j2=j1; j1=0; m=1;}
  168.   else {if (arry[1][j1][j2][j3][j4]=='Y')
  169.     {arry[1][j1][j2][j3][j4]='y';
  170.     k=j4; j4=j3; j3=j2; j2=j1; j1=1; m=1;}
  171.   else {if (arry[2][j1][j2][j3][j4]=='Y')
  172.     {arry[2][j1][j2][j3][j4]='y';
  173.     k=j4; j4=j3; j3=j2; j2=j1; j1=2; m=1;}
  174.   else {if (arry[3][j1][j2][j3][j4]=='Y')
  175.     {arry[3][j1][j2][j3][j4]='y';
  176.     k=j4; j4=j3; j3=j2; j2=j1; j1=3; m=1;}
  177.   else {l=1; if(m==1) {j0=j1; j1=j2; j2=j3; j3=j4; j4=k;}; };};};};
  178.   } while (l==0);
  179. l=0; 
  180. m=0;
  181. do {
  182.         if (arry[j0][j1][j2][j3][0]=='y')
  183.    {prf(j0,j1,j2,j3,0);
  184.    arry[j0][j1][j2][j3][0]='N';
  185.    j0=j1; j1=j2; j2=j3; j3=0; m=1;}
  186.   else {if (arry[j0][j1][j2][j3][1]=='y')
  187.    {prf(j0,j1,j2,j3,1);
  188.    arry[j0][j1][j2][j3][1]='N';
  189.    j0=j1; j1=j2; j2=j3; j3=1; m=1;}
  190.   else {if (arry[j0][j1][j2][j3][2]=='y')
  191.    {prf(j0,j1,j2,j3,2);
  192.    arry[j0][j1][j2][j3][2]='N';
  193.    j0=j1; j1=j2; j2=j3; j3=2; m=1;}
  194.   else {if (arry[j0][j1][j2][j3][3]=='y')
  195.    {prf(j0,j1,j2,j3,3);
  196.    arry[j0][j1][j2][j3][3]='N';
  197.    j0=j1; j1=j2; j2=j3; j3=3; m=1;}
  198.   else {l=1;};};};};
  199.   } while (l==0);
  200. l=0;
  201. do {
  202.         if (arry[j0][j1][j2][j3][0]=='Y')
  203.    {prf(j0,j1,j2,j3,0);
  204.    arry[j0][j1][j2][j3][0]='N';
  205.    j0=j1; j1=j2; j2=j3; j3=0; m=1;}
  206.   else {if (arry[j0][j1][j2][j3][1]=='Y')
  207.    {prf(j0,j1,j2,j3,1);
  208.    arry[j0][j1][j2][j3][1]='N';
  209.    j0=j1; j1=j2; j2=j3; j3=1; m=1;}
  210.   else {if (arry[j0][j1][j2][j3][2]=='Y')
  211.    {prf(j0,j1,j2,j3,2);
  212.    arry[j0][j1][j2][j3][2]='N';
  213.    j0=j1; j1=j2; j2=j3; j3=2; m=1;}
  214.   else {if (arry[j0][j1][j2][j3][3]=='Y')
  215.    {prf(j0,j1,j2,j3,3);
  216.    arry[j0][j1][j2][j3][3]='N';
  217.    j0=j1; j1=j2; j2=j3; j3=3; m=1;}
  218.   else {l=1; if (m==1) kwait(0);};};};};
  219.   } while (l==0);
  220. };};};};};
  221. }
  222.  
  223. /* print one link of the de Bruijn diagram */
  224. prf(i0,i1,i2,i3,i4) int i0, i1,i2, i3, i4; {
  225. kwait(1);
  226. printf("%1d",i0);
  227. printf("%1d",i1);
  228. printf("%1d",i2);
  229. printf("%1d",i3);
  230. printf("-");
  231. printf("%1d",i4);
  232. printf(" ");}
  233.  
  234. /* print the entire array of links */
  235. /* feasible only during debugging  */
  236. pall() {
  237. int i0, i1, i2, i3, i4;
  238. for (i0=0; i0<4; i0++) {
  239. for (i1=0; i1<4; i1++) {
  240. for (i2=0; i2<4; i2++) {
  241. for (i3=0; i3<4; i3++) {
  242. for (i4=0; i4<4; i4++) {
  243. printf("%c",arry[i0][i1][i2][i3][i4]);
  244. };};};};};
  245. printf("\n");
  246. }
  247.  
  248. /* keyboard status */
  249. kbdst() {return bdos(11)&0xFF;}
  250.  
  251. /* direct keyboard input, no echo */
  252. kbdin() {int c;
  253. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  254. return c;}
  255.  
  256. /* pause at the end of a full screen */
  257. kwait(i) int i; {
  258. switch (i) {
  259.   case 0: printf("\n"); nc=0; nl++; break;
  260.   case 1: if (nc==MC) {printf("&\n"); nc=1; nl++;} else nc++; break;
  261.   default: break;};
  262. if (nl==NW) {
  263.   nl=0;
  264.   printf(" press any key to continue\015");
  265.   while (kbdst()) {};
  266.   kbdin();
  267.   printf("-                         \n");
  268.   };
  269. }
  270.  
  271. /* end */
  272.